package com.code.nowcoder.other;

import com.code.nowcoder.utils.Point;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/28 19:36
 */
public class The85_AC {
    /**
     * 能回到1号点返回 Yes，否则返回 No
     *
     * @param param int整型一维数组 param[0] 为 n，param[1] 为 m
     * @param edge  Point类一维数组 Point.x , Point.y 分别为一条边的两个点
     * @return string字符串
     */
    public String solve(int[] param, Point[] edge) {
        // write code here
        // 寻找1号格子
        int n = param[0];
        int m = param[1];
        if (m >= 100000) {
            return "No";
        }
        /*
          这个地方有些问题，如果使用 n 的话，后面如有超过 n 都带有 1 的话，导致越界
         */
        int[] temp = new int[n];
        int index = 0;
        // 存储 temp 长度的变量
        int num = 0;
        // 将带有原点的通道都找出来，并且将另一个数放在生成的数组中
        for (Point p : edge) {
            if (p.x == 1 || p.y == 1) {
                temp[index] = p.x == 1 ? p.y : p.x;
                index++;
                num++;
            }
        }
        // 如果只有一个通道有 1 的话，永远也产生不出回路
        if (num < 2) {
            return "No";
        }
        int temIndex = ++index;
        // 少占用空间？
        Point p = null;
        // 循环 temp 数组，也就是存储带有 1 通道的 Point
        for (int i = 0; i < temIndex; i++) {
            for (int j = 0; j < m; j++) {
                // 每次都将 edge 循环一次
                p = edge[j];
                // 如果得到的 point 中的 x, y 符合在 temp 数组中的话，
                if (p.x == temp[i] || p.y == temp[i] && j != num) {
                    if (p.x == temp[i] && !exists(p.y, temp)) {
                        temp[index++] = p.y;
                    } else if (!exists(p.x, temp)) {
                        temp[index++] = p.x;
                    }
                    if (temp[index - 1] == 1) {
                        return "Yes";
                    }
                }
            }
            temIndex = index;
        }
        return "No";
    }

    public static boolean exists(int x, int[] arr) {
        for (int value : arr) {
            if (value == x) return true;
        }
        return false;
    }
}
